/*  
 *  Copyright 2006 Paul Jack.
 *
 *  This file is part of the Dex compiler suite. 
 *  
 *  Dex is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU General Public License as published by the
 *  Free Software Foundation; either version 2 of the License, or (at your
 *  option) any later version.
 *  
 *  Dex is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
 *  Public License for more details.
 *  
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
 */
package dex.machine;

import java.util.ArrayList;
import java.util.List;


/**
 *  Naive implementation of the Memory interface.
 *  
 *  <p>The "heap" is actually a sequential list of blocks.  The contents
 *  are represented as an internal array of 32-bit int values.
 *
 *  <p>Memory is allocated using a simple "first fit" algorithm.
 *  The {@link TypeDescriptor} object used during the allocation is saved
 *  into a list.  Each entry in the descriptor list is unique; so if you
 *  allocated 100 Foo objects and 39 Baz objects, the descriptor list
 *  will only contain 2 entries, one for the Foo descriptor and one for
 *  the Baz descriptor.  The descriptor list allows types to be referenced
 *  using a <i>type index</i>, which is simply the index in the descriptor
 *  list for a particular type.
 *  
 *  <p>Blocks of memory are preceded by a header word (32 bits).  The
 *  most significant bit of the header word determines whether the block
 *  is free or empty.  The other bits of the header word describe different
 *  things for the two cases.
 *  
 *  <p>If the block is free, then the lower 31 bits of the header word 
 *  contain the size, in 8-bit bytes, of the free space.  This will always
 *  be a multiple of 4.
 *  
 *  <p>If the block is busy, then second most significant bit of the header
 *  determines whether or not the garbage collector has marked the block.
 *  The third most significant bit of the header determines whether the 
 *  block contains an array or a non-array.  The lower 29 bits form the
 *  type index.  In order to determine the size of a busy block, one must
 *  first look up the TypeDescriptor using the type index, and then 
 *  retrieve the size from the TypeDescriptor.
 *  
 *  <p>The 32-bit header word is the only overhead imposed on every block.
 *  
 *  <p>
 *  
 */
public class SimpleMemory implements Memory {

	
	/**
	 * The minimum size of a block of memory.
	 */
	final static int MIN_BLOCK = 4;
	
	
	/**
	 * The memory.  Do not alter directly; can be altered with the various
	 * poke and peek methods.
	 * This is modelled as an array of int, as opposed to byte, because 90%
	 * of the time we want to fetch and store 32-bit values.
	 */
	int[] memory;
	
	
	Roots roots;
	
	List<TypeDescriptor> typeCache;
	
	AddressKeeper addresses;
	
	
	/**
	 *  Constructs a new "heap" of memory with the given size.
	 */
	public SimpleMemory(Roots roots, int initialSize) {
		if (initialSize <= 0) {
			throw new IllegalArgumentException("initialSize must be positive.");
		}
		this.memory = new int[adjustRequestedSize(initialSize) / MIN_BLOCK];
		this.roots = roots;		
		poke(0, memory.length * 4 - 4);
		this.typeCache = new ArrayList<TypeDescriptor>();
		this.addresses = new HashAddressKeeper();
	}
	
	
	public int getSize() {
		return memory.length * 4;
	}
	
	
	/**
	 *  Stores the given value at the given offset.
	 *  32-bit values are aligned to 4-byte boundaries; so the given offset must be 
	 *  a multiple of 4.
	 *  
	 *  @param offset  The offset where to store the value
	 *  @param value   The value to store
	 *  @throws AlignmentException  if the given ofset is not aligned to a 4-byte boundary
	 */
	public void poke(int offset, int value) {
		if (offset % 4 != 0) {
			throw new AlignmentException(offset, 4);
		}
		memory[offset / 4] = value;
	}
	
	
	public short peekShort(int offset) {
		if (offset % 2 != 0) {
			throw new AlignmentException(offset, 2);
		}
		int r = memory[offset / 4];
		int shift = (offset % 4) * 8;
		return (short)((r >> shift) & 0xFFFF);
	}
	
	
	public byte peekByte(int offset) {
		int r = memory[offset / 4];
		int shift = (offset % 4) * 8;
		return (byte)((r >> shift) & 0xFF);
	}
	
	public void poke(int offset, byte value) {
		int shift = (offset % 4) * 8;
		int mask = ~(0xFF << shift);
		int shiftedByte = (value & 0xFF) << shift;
		int oldInt = memory[offset / 4];
		memory[offset / 4] = oldInt & mask | shiftedByte;
	}

	
	public void poke(int offset, short value) {
		if (offset % 2 != 0) {
			throw new AlignmentException(offset, 2);
		}
		int shift = (offset % 4) * 8;
		int mask = ~(0xFFFF << shift);
		int shiftedShort = (value & 0xFFFF) << shift;
		int oldInt = memory[offset / 4];
		memory[offset / 4] = oldInt & mask | shiftedShort;
	}
	
	
	/**
	 *  Returns the 32-bit value at the given offset.
	 *  32-bit values are aligned to 4-byte boundaries; so the given offset must be 
	 *  a multiple of 4.
	 *  
	 *  @param offset  The offset whose value to return
	 *  @return  The 32-bit value at that offset
	 *  @throws AlignmentException  if the given ofset is not aligned to a 4-byte boundary
	 */
	public int peekInt(int offset) {
		if (offset % 4 != 0) {
			throw new AlignmentException(offset, 4);
		}
		return memory[offset / 4];
	}
	
	
	
	public void setField(int object, int offset, int reference) {
		if (object == 0) {
			throw new IllegalStateException("Attempted to set field on NULL");
		}
		validateReference(object);
		Block block = new Block(this, object - 4);
		if (block.isArray()) {
			throw new IllegalStateException("Attempted to set field on array address.");
		}
		if (block.isFree()) {
			throw new IllegalStateException("Keeper said valid address, but block is free.");
		}
		if (reference != 0) {
			validateReference(reference);
		}
		IntIterator offsets = block.getTypeDescriptor().getReferenceOffsets();
		while (offsets.hasNext()) {
			int o = offsets.next();
			if (o == offset) {
				poke(object + o, reference);
				return;
			}
		}
		throw new IllegalStateException(offset + " is not a valid reference offset for " + object);
	}
	
	
	private void validateReference(int reference) {
		if (!addresses.isValidAddress(reference)) {
			throw new IllegalStateException(reference + " is not a valid object address.");
		}
		Block block = new Block(this, reference - 4);
		if (block.isFree()) {
			throw new IllegalStateException(reference + ": keeper said valid, but block is free.");
		}
	}

	int getTypeIndex(TypeDescriptor type) {
		int max = typeCache.size();
		for (int i = 0; i < max; i++) {
			TypeDescriptor t = typeCache.get(i);
			if (t.equals(type)) {
				return i;
			}
		}
		typeCache.add(type);
		return max;
	}
	
	
	TypeDescriptor getTypeDescriptor(int index) {
		return typeCache.get(index);
	}
	
	
	void grow() {
		// Find the last block.  
		Block lastBlock = getLastBlock();
		
		// Expand the array storing the memory.
		long newSize = (long)memory.length * 8L;
		
		// Block header stores sizes as 30 bits,
		// so if the new heap size is any larger than 2^30,
		// we're exhausted.
		long maxSize = (1 << 30);
		if (newSize > maxSize) {
			throw new OutOfMemoryError();
		}
		
		int[] temp = memory;
		memory = new int[temp.length * 2];
		System.arraycopy(temp, 0, memory, 0, temp.length);
		
		if (lastBlock.isFree()) {
			// If the last block was free, add the newly allocated space
			// to its size.
			lastBlock.setInfo(lastBlock.getInfo() + temp.length * 4);
		} else {
			// Otherwise, create a new block after the last block, and
			// set its available space to the newly allocated space minus header size
			poke(temp.length * 4, temp.length * 4 - 4);
		}
	}
	
	
	Block getLastBlock() {
		// FIXME: This works, but it's O(n).
		// It should be easy to keep
		// track of a "maxAddress" that would point to the
		// last block.  maxAddress would be updated during
		// allocations and during garbage collection.
		// Then this method would simply return 
		// new Block(this, maxAddress - 4), an O(1) operation.
		
		Block previous = null;
		Block current = new Block(this, 0);
		while (current != null) {
			previous = current;
			current = current.getNextBlock();
		}
		return previous;
	}
	
	
	public int allocateArray(TypeDescriptor type, int arraySize) {
		return allocate2(type, arraySize);
	}
	
	
	public int allocate(TypeDescriptor type) {
		return allocate2(type, -1);
	}
	
	
	private int allocate2(TypeDescriptor type, int arraySize) {
		int result = allocate3(type, arraySize);
		if (result != 0) {
			addresses.addAddress(result);
		}
		return result;
	}
	
	
	private int allocate3(TypeDescriptor type, int arraySize) {
		int result = attemptAllocate(type, arraySize);
		if (result != 0) {
			return result;
		}
		if (roots != null) {
			garbageCollect();
			result = attemptAllocate(type, arraySize);
			if (result != 0) {
				return result;
			}
		}
		grow();
		result = attemptAllocate(type, arraySize);
		return result;
	}
	
	
	int attemptAllocate(TypeDescriptor type, int arraySize) {
		int size = calculateSize(type, arraySize);
		Block block = new Block(this, 0);
		while (block != null) {
			if (block.isFree() && block.getDataSize() >= size) {
				block.allocate(type, arraySize);
				return block.getDataAddress();
			}
			block = block.getNextBlock();
		}
		return 0; // FIXME
	}
	
	
	public void garbageCollect() {
		if (roots == null) {
			return;
		}
		IntIterator rootAddresses = roots.getRoots();
		while (rootAddresses.hasNext()) {
			int address = rootAddresses.next();
			mark(address);
		}
		Block previous = null;
		Block current = new Block(this, 0);
		while (current != null) {
			if (current.isMarked()) {
				current.setMarked(false);
			} else if (!current.isFree()) {
				addresses.removeAddress(current.getDataAddress());
				current.free();
			}
			if ((previous != null) && previous.isFree() && current.isFree()) {
				previous.mergeFreeWithNext();
				current = previous.getNextBlock();
			} else {
				previous = current;
				current = current.getNextBlock();
			}
		}
	}


	void mark(int address) {
		if (address == 0) {
			// Null pointer, nothing to mark
			return;
		}
		if (!addresses.isValidAddress(address)) {
			throw new IllegalStateException("No such address: " + address);
		}
		Block block = new Block(this, address - 4);
		if (block.isMarked()) {
			return;
		}
		if (block.isFree()) {
			throw new IllegalStateException("Reachable free block.");
		}
		block.setMarked(true);
		TypeDescriptor type = block.getTypeDescriptor();
		if (type.isPrimitive()) {
			return;
		}
		if (block.isArray()) {
			markArrayContents(block, type);
		} else {
			markNonArrayContents(block, type);
		}
	}
	
	
	private void markNonArrayContents(Block block, TypeDescriptor type) {
		int address = block.getDataAddress();
		IntIterator refs = type.getReferenceOffsets();
		while (refs.hasNext()) {
			int fieldOffset = refs.next();
			int fieldAddress = address + fieldOffset;
			int addressToMark = peekInt(fieldAddress);
			mark(addressToMark);
		}		
	}
	
	
	private void markArrayContents(Block block, TypeDescriptor type) {
		int arrayAddress = block.getDataAddress();
		int arraySize = peekInt(arrayAddress);
		int elementSize = adjustRequestedSize(type.getSize());
		for (int i = 0; i < arraySize; i++) {
			int elementAddress = arrayAddress + 4 + elementSize * i;
			IntIterator refs = type.getReferenceOffsets();
			while (refs.hasNext()) {
				mark(peekInt(elementAddress + refs.next()));
			}
		}
		
	}


	/**
	 *  Adjusts the given size so that it's a multiple of 8, because
	 *  8 is the minimum block size.
	 */
	static int adjustRequestedSize(int size) {
		if (size < 0) {
			throw new IllegalArgumentException();
		}
		if (size % MIN_BLOCK == 0) {
			return size;
		}
		return size / MIN_BLOCK * MIN_BLOCK + MIN_BLOCK;
	}

	
	static int calculateSize(TypeDescriptor type, int arraySize) {
		int adjusted = adjustRequestedSize(type.getSize());
		if (arraySize < 0) {
			return adjusted;
		}
		// FIXME: For instance, byte arrays
		return 4 + arraySize * adjusted;
	}

}
